package leetcode_700;

/**
 *@author 周杨
 *PalindromicSubstrings_647 计算一个字符串里子串是回文串的个数
 *describe:用动态规划 回文串的构造依赖于更小规模的回文串 AC 57%
 *2018年9月26日 下午12:12:40
 */
public class PalindromicSubstrings_647 {
	public int countSubstrings(String s) {
        if(s.length()<2)
        	return s.length();
        boolean dp[][]=new boolean[s.length()][s.length()];
        int res=1;
        char chars[]=s.toCharArray();
        dp[0][0]=true;
        for(int i=1;i<s.length();++i) {
        	dp[i][i]=true;
        	++res;
        	for(int j=0;j<i;++j) {
        		if(chars[i]==chars[j]) {
        			if(j+1==i) {//中间没有元素
        				dp[j][i]=true;
        				++res;
        			}
        			else {
        				if(dp[j+1][i-1]){
        					dp[j][i]=true;
        					++res;
        				}
        			}
        		}
        	}
        }
        return res;
    }
}
